package cumt.oj;

/**
 * @Author Fizz Pu
 * @Date 2020/11/17 下午2:54
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

import java.lang.reflect.Array;
import java.util.*;

/**
 * 题目描述
 * 你来到一个迷宫前。该迷宫由若干个房间组成，每个房间都有一个得分，第一次进入这个房间，
 * 你就可以得到这个分数。还有若干双向道路连结这些房间，
 * 你沿着这些道路从一个房间走到另外一个房间需要一些时间。
 * 游戏规定了你的起点和终点房间，你首要目标是从起点尽快到达终点，
 * 在满足首要目标的前提下，使得你的得分总和尽可能大。
 * 现在问题来了，给定房间、道路、分数、起点和终点等全部信息，
 * 你能计算在尽快离开迷宫的前提下，你的最大得分是多少么？
 *
 * 输入
 * 第一行4个整数n (<=500), m, start, end。n表示房间的个数，房间编号从0到(n - 1)，m表示道路数,任意两个房间之间最多只有一条道路，start和end表示起点和终点房间的编号。
 *
 * 第二行包含n个空格分隔的正整数(不超过600)，表示进入每个房间你的得分。
 *
 * 再接下来m行，每行3个空格分隔的整数x, y, z (0<z<=200)表示道路,表示从房间x到房间y(双向)的道路,注意，最多只有一条道路连结两个房间,你需要的时间为z。
 *
 * 输入保证从start到end至少有一条路径。
 *
 * 输出
 *  占一行，分别最短时间和相应的最大得分，中间用空格隔开。
 * 样例输入
 * 3 2 0 2
 * 1 2 3
 * 0 1 10
 * 1 2 11
 * 样例输出
 * 21 6
 */

// 初步解决方案
// 1. DFS暴力搜索, 选出单位时间内得分最高的哪个



class PossibleRes implements Comparable<PossibleRes>{
    int socre;
    int time;

    public PossibleRes(int socre, int time) {
        this.socre = socre;
        this.time = time;
    }

    public void setSocre(int socre) {
        this.socre = socre;
    }

    public void setTime(int time) {
        this.time = time;
    }

    @Override
    public int compareTo(PossibleRes o) {
        if(time == 0 || o.time == 0) return this.socre - o.socre;
        return  ((double)this.socre/ this.time) > ((double)(this.socre / this.time)) ? 1 : -1;
    }

    @Override
    public String toString(){
        return this.time + " " + this.socre;
    }

    public PossibleRes(){}
}

class Maz {
    private int[] scores; // 下标为i的节点分数为scores[i]
    private Map<Integer , List<ArrayList<Integer>>> nextArr; // {0:[[1,3],[4,5]]} 表示0号节点的下一个可能为1,4, 对应的时间分别为3, 5
    private ArrayList<PossibleRes> arrayList = new ArrayList<>();

    public Maz(int[] scores, Map<Integer, List<ArrayList<Integer>>> next) {
        this.scores = scores;
        this.nextArr = next;
    }

    public void get(int start, int end){
        if(arrayList == null || arrayList.size() == 0) searchMaze(start, end, null);

        // 找到最优解

        PossibleRes max = null;
        for(PossibleRes possibleRes: arrayList){
            if(max == null) max = possibleRes;
            else {
                if(max.compareTo(possibleRes) < 0) max = possibleRes;
            }
        }
        System.out.println(max);
    }


    private void searchMaze(int start, int end, PossibleRes res){

        if(res == null) res = new PossibleRes();
        res.setSocre(res.socre + scores[start]);

        if(start == end){
            arrayList.add(new PossibleRes(res.socre, res.time)); // 复制一份
        }
        else{
            List<ArrayList<Integer>> next = nextArr.get(start);
            for (ArrayList<Integer> integers : next) {
                int nextNode = integers.get(0);
                int time = integers.get(1);
                res.setTime(res.time + time);
                searchMaze(nextNode, end, res); // 搜索下一节点
                res.setTime(res.time - time);     // 回溯
                res.setSocre(res.socre-scores[nextNode]);
            }
        }
    }
}

public  class  Maze{
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int houseCount = scanner.nextInt();
        int pathCount = scanner.nextInt();
        int start = scanner.nextInt();
        int end = scanner.nextInt();

        int[] scores = new int[houseCount];
        for(int i = 0; i < houseCount; ++i){
            scores[i] = scanner.nextInt();
        }

        Map<Integer, List<ArrayList<Integer>>> next = new HashMap<>(houseCount);

        for(int i = 0; i < pathCount; ++i){
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int time = scanner.nextInt();

            if(!next.containsKey(x)){
                next.put(x, new ArrayList<ArrayList<Integer>>());
            }
            ArrayList<Integer> inner = new ArrayList<>();
            inner.add(y);
            inner.add(time);
            Collections.addAll(next.get(x), inner);
        }

        // List<ArrayList> 内部无法支持泛型
        Maz maze = new Maz(scores, next);
        maze.get(start, end);
        

    }
}

